128
11
Randomness and Complexity
11.3
Random Walks
Consider an agent on a line susceptible to step right along the line with probability
pp and left with probability q equals 1 minus pq = 1 −p. We can encode the walk by writing plus 1+1 for a
right step and negative 1−1 for a left step. Many processes can be mapped onto the random
walk (e.g., a nucleic acid sequence, with purines identical to negative 1≡−1 and pyrimidines identical to plus 1≡+1). If
the walk is drawn in Cartesian coordinates as a polygon with the number of steps
(“time”) along the horizontal axis and the displacement along the vertical axis, then
if s Subscript ksk is the partial sum of the first kk steps,
sk − sk−1 = ±1,
s0 = 0,
sn = n(p − q) ,
(11.12)
where nn is the length of the path.
Definition. Letn greater than 0n > 0 andxx be integers. A pathleft parenthesis s 1 comma s 2 comma ellipsis comma s Subscript n Baseline right parenthesis(s1, s2, . . . , sn) from the origin to the
pointleft parenthesis n comma x right parenthesis(n, x)is a polygonal line whose vertices have abscissae0 comma 1 comma ellipsis comma n0, 1, . . . , nand ordinates
s 0 comma s 1 comma ellipsis comma s Subscript n Baselines0, s1, . . . , sn satisfyings Subscript k Baseline minus s Subscript k minus 1 Baseline equals epsilon Subscript k Baseline equals plus or minus 1 comma s 0 equals 0sk −sk−1 = εk = ±1, s0 = 0, ands Subscript n Baseline equals p minus qsn = p −q (wherepp and
qq are now the numbers of symbols, p plus q equals np + q = n), with s Subscript n Baseline equals xsn = x.
There are 2 Superscript n2n paths of length nn, but a path from the origin to an arbitrary point
left parenthesis n comma x right parenthesis(n, x) exists only if nn and xx satisfy
n = n(p + q),
x = n(p − q) .
(11.13)
In this case, the n pnp positive steps can be chosen from among the nn available places
in
Nn,x =
(p + q
p
)
=
(p + q
q
)
(11.14)
ways. The average distance travelled afternn steps istilde n Superscript 1 divided by 2∼n1/2, and the variance increases
linearly with the number of steps.
Diffusion is an example of a random walk. The diffusivity (diffusion coefficient)
upper DD that gives the constant of proportionality in Fick’s first and second laws 9 is given
9 Fick’s first law is
Ji = −Di∇ci ,
(11.15)
where upper JJ is the flux of substance ii across a plane and cc is its (position-dependent) concentration.
In one dimension, this law simply reduces toupper J equals negative upper D partial differential c left parenthesis x right parenthesis divided by partial differential xJ = −D∂c(x)/∂x, wherexx is the spatial coordinate.
In most cases, especially in the crowded milieu of a living cell, it is more appropriate to use the
(electro)chemical potentialmuμ than the concentration, whereupon the law becomes
Ji = −Di∇μi(ci/kBT )
(11.16)
whereupper TT is the absolute temperature. Fick’s second law, appropriate for time-varying concentrations,
is
∂c/∂t = D∇2c .
(11.17)